package graph;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class PrimJ {

    public static List<Vertex> vertexList = new ArrayList<>();//节点集合
    public static List<Edge> edgeQueue = new ArrayList<>();//边集合
    public static List<Vertex> newVertex = new ArrayList<>();//已经访问的节点集合

    public static void main(String[] args){
        primTree();
    }

    public static void buildGraph(){
        Vertex v1 = new Vertex("a");
        PrimJ.vertexList.add(v1);

        Vertex v2 = new Vertex("b");
        PrimJ.vertexList.add(v2);

        Vertex v3 = new Vertex("c");
        PrimJ.vertexList.add(v3);

        Vertex v4 = new Vertex("d");
        PrimJ.vertexList.add(v4);

        Vertex v5 = new Vertex("e");
        PrimJ.vertexList.add(v5);


        addEdge(v1,v2,6);
        addEdge(v1,v3,7);
        addEdge(v2,v3,8);
        addEdge(v2,v5,4);
        addEdge(v2,v4,5);
        addEdge(v3,v4,3);
        addEdge(v3,v5,9);
        addEdge(v5,v4,7);
        addEdge(v5,v1,2);
        addEdge(v4,v2,2);
    }

    public static void primTree(){
        buildGraph();
        Vertex start = vertexList.get(0);
        newVertex.add(start);

        for(int n = 0;n<vertexList.size()-1;n++){
           Vertex temp = new Vertex(start.key);
           Edge tempEdge = new Edge(start,start,1000);
           for(Vertex v:newVertex){
               for(Edge e:edgeQueue){
                   if(e.start == v&&!containVertex(e.end)){
                       if(e.key<tempEdge.key){
                           temp = e.end;
                           tempEdge = e;
                       }
                   }
               }
           }
            newVertex.add(temp);
        }

        Iterator<Vertex> it = newVertex.iterator();
        while(it.hasNext()){
            Vertex v = it.next();
            System.out.println("key:  "+v.key);
        }

    }

    public static boolean containVertex(Vertex vertex){
        for(Vertex v:newVertex){
            if(v.key.equals(vertex.key))
                return true;
        }
        return false;
    }

    public static void addEdge(Vertex a,Vertex b,int w){
        Edge e = new Edge(a,b,w);
        PrimJ.edgeQueue.add(e);
    }

    static class Vertex{
        String key;

        public Vertex(String key) {
            this.key = key;
        }
    }

    public static class  Edge{
        Vertex start;
        Vertex end;
        int key;

        public Edge(Vertex start, Vertex end, int key) {
            this.start = start;
            this.end = end;
            this.key = key;
        }
    }
}
